#include <stdlib.h>     //rand, malloc
#include <stdio.h>      //print
#include <time.h>

typedef struct no{
    int numero;
    struct no *proximo;
    struct no *anterior;
}No;

//Finds length of list, which is usefull in selecting a random pivot
int ListLength (No *list)
{
    No *temp = list;
    int i=0;
    while(temp!=NULL)
    {
        i++;
        temp=temp->proximo;
    }
    return i;
}

// Selects a random pivot point
No *SelectPivot(No *list)
{
    int k, n, i = 0;
    n = ListLength(list);
    No *pivot=list;
    k=rand()%n;  //
    for (; i < k; ++i)
    {
        pivot=pivot->proximo;
    }
    return pivot;
}

// Sorts a list using quicksort algo with random pivot point
No *Quicksort(No *list)
{
    // Return NULL list
    if (ListLength(list) <= 1) return list;
    No *less=NULL, *more=NULL, *next, *end, *temp=NULL;

    // Select a random pivot point
    No *pivot = SelectPivot(list);

    // Remove pivot from list
    while(list !=NULL)
    {
        next = list->proximo;

        if(list->numero != pivot->numero)
        {
            list->proximo=temp;
            temp = list;
        }
        list = next;
    }

    // Divide & Conq
    while(temp != NULL)
    {
        next = temp->proximo;
        if(temp->numero < pivot->numero)
        {
            temp->proximo = less;
            less = temp;
        }
        else
        {
            temp->proximo = more;
            more = temp;
        }
        temp = next;
    }

    // Recursive Calls
    less = Quicksort(less);
    more = Quicksort(more);

    // Merge
    if(less != NULL)
    {
        end = less;
        while(end->proximo != NULL){
            end=end->proximo;
            }
        pivot->proximo=more;
        end->proximo = pivot;
        return less;
    }
    else{
        pivot->proximo = more;
        return pivot;
    }

}

void add_node(struct no **head, int value)
{
  No *temp, *cur;
  temp = (No *)malloc(sizeof(No));
  temp->proximo=NULL;
  temp->anterior=NULL;

  if(*head == NULL)
  {
     *head=temp;
     temp->numero=value;
  }
  else
  {
   for(cur=*head;cur->proximo!=NULL;cur=cur->proximo);
   cur->proximo=temp;
   temp->anterior=cur;
   temp->numero=value;
  }
}

void salvaListaNoArquivo(No *cabeca, char nomeArquivo[]){
	FILE *fp;
	int resultado;
	No *noCorrente;

	fp = fopen (nomeArquivo, "w");
	if (fp == NULL) {
		printf ("Houve um erro ao abrir o arquivo.\n");
		return ;
	}


	noCorrente = cabeca;
	while( noCorrente != NULL ) {
		resultado = fprintf(fp,"%i ", noCorrente->numero);
		if (resultado == EOF){
			printf("Erro na Gravacao\n");
			return;
		}
		noCorrente = noCorrente->proximo;
	}

	fclose (fp);

}

void liberarLista(No *cabeca)
{

	No *noAtual = cabeca;
	while(noAtual != NULL)
	{
		No *temporario = noAtual;
		noAtual = noAtual->proximo;
		free(temporario);
	}
}
//
//int main(int argc,char *argv[]){
//   No *cabeca, *final;
//   cabeca = (struct no *)NULL;
//
//
//
//	int numeroArquivo = 0;
//	FILE *fp;
//
//	fp = fopen (argv[1], "r");
//
//	while(fscanf(fp,"%d", &numeroArquivo) != EOF){
//
//		if (numeroArquivo != '\0' && numeroArquivo != EOF) {
//			add_node(&cabeca, numeroArquivo);
//		}
//	}
//	fclose (fp);
//
//	//mergeSort(&cabeca);
//	final = Quicksort(cabeca);
//	salvaListaNoArquivo(final, argv[2]);
//
//	liberarLista(cabeca);
//
//	return 0;
//}
